package q675_cutOffTree;

import java.util.*;

public class Solution {
    private static final int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    public static int cutOffTree(List<List<Integer>> forest) {
        // 对树按高度排序：
        int m = forest.size(), n = forest.get(0).size();
        ArrayList<int[]> heights = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int h = forest.get(i).get(j);
                if (h > 1) heights.add(new int[]{i,j,h});
            }
        }
        System.out.println(heights);
        // height中将会按照树的高度进行排序 并且记录了每一个树的位置 i j
        Collections.sort(heights, Comparator.comparingInt(o -> o[2]));

        // 搜索(0,0)到第1颗树的最短距离：
        int step = minDistance(forest, 0, 0, heights.get(0)[0], heights.get(0)[1]);
        if (step == -1) return -1;
        // 搜索高度从低到高各颗树之间的最短距离：
        for (int i = 0; i < heights.size()-1; i++) {
            int[] from = heights.get(i), to = heights.get(i+1);
            int s = minDistance(forest, from[0], from[1], to[0], to[1]);
            if (s == -1) return -1;
            step += s;
        }
        return step;
    }

    // BFS暴力搜索from->to最短路径
    private static int minDistance(List<List<Integer>> forest, int fromRow, int fromCol, int toRow, int toCol) {
        int m = forest.size(), n = forest.get(0).size();
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        queue.add(new int[]{fromRow,fromCol});
        visited[fromRow][fromCol] = true;

        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] node = queue.poll();
                int row = node[0], col = node[1];
                if (row == toRow && col == toCol) return step;
                for (int[] dir : dirs) {
                    int nextRow = row+dir[0], nextCol = col+dir[1];
                    if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && !visited[nextRow][nextCol] && forest.get(nextRow).get(nextCol) != 0) {
                        queue.add(new int[]{nextRow, nextCol});
                        visited[nextRow][nextCol] = true;
                    }
                }

            }
            step++;
        }
        return -1;
    }


}
